Persistent devices, particularly solid state drives (“SSD”), provide a faster alternative to hard disk drives for storing data, but often come at a higher cost. One common use of a SSD is as a cache, wherein data that is needed immediately can be stored for quick access relative to a full storage medium.
However, where fast storage is used as a cache for a large file system, it becomes important to have an efficient process by which unneeded data can be evicted from the cache to make room for newer data. A variety of eviction algorithms for determining which cache files are the best candidates for removal from the cache are known in the art. Known eviction algorithms include LRU and L2ARC. These algorithms consume memory and processing time because ordered lists have to be maintained and updated with every access.
For example, one eviction technique is known as a “two-hand clock” algorithm. In this algorithm, each cache file is flagged whenever the file is used by the system. The system periodically sweeps the cache and turns off flags; files that are not flagged are eligible for eviction. This allows the system to preserve recently-used files in the cache while evicting files that have not been used since the most recent clock sweep. This algorithm may sometimes be less precise in choosing eviction candidates but requires significantly less memory and processing time than many other algorithms.
One potential problem with eviction algorithms, including the standard “two-hand clock” algorithm, is that large files may sometimes take up a significant portion of the cache even though only small portions of the files are actually accessed. To the extent that traditional algorithms evaluate access on a file basis only, this can result in an inefficient use of cache memory.
In view of the foregoing, it may be understood that there may be significant problems and shortcomings associated with current file system technologies.